package club.xiaojiawei.dp;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/9/22 5:00 PM
 * @question 516. 最长回文子序列
 * @description 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
 * 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
 */
public class LongestPalindromeSubSeq516 {

    public static void main(String[] args) {
        LongestPalindromeSubSeq516 test = new LongestPalindromeSubSeq516();
        int result = test.longestPalindromeSubseq3("babbab");
        System.out.println(result);
    }

    /**
     * dpa
     * @param s
     * @return
     */
    public int longestPalindromeSubseq(String s) {
        int length = s.length();
        if (length < 2){
            return length;
        }
        char[] chars = s.toCharArray();
        int[][] dp = new int[length + 1][length + 1];
        int temp;
        for (int i = 1; i <= length; i++) {
            dp[i][i] = 1;
            temp = chars[i - 1];
            for (int j = i - 1; j > 0; j--) {
                if (temp == chars[j - 1]){
                    dp[j][i] = dp[j + 1][i - 1] + 2;
                }else {
                    dp[j][i] = Math.max(dp[j][i - 1], dp[j + 1][i]);
                }
            }
        }
        return dp[1][length];
    }

    /**
     * 官方-dp
     * @param s
     * @return
     */
    public int longestPalindromeSubseq2(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            char c1 = s.charAt(i);
            for (int j = i + 1; j < n; j++) {
                char c2 = s.charAt(j);
                if (c1 == c2) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }

    /**
     * 民间-dp（nb）
     * @param s
     * @return
     */
    public int longestPalindromeSubseq3(String s) {
        int n = s.length();
        int[] dp = new int[n];
        char[] ch = s.toCharArray();
        int max = 0;
        for (int j = 0; j < n; j++) {
            dp[j] = 1;
            max = 0;
            for (int i = j - 1; i >= 0; i--) {
                int length = dp[i];
                if (ch[i] == ch[j]) {
                    dp[i] = max + 2;
                }
                max = Math.max(max, length);
            }
        }
        for (int num : dp) max = Math.max(max, num);
        return max;
    }
}
